package LeetCode75;

import publicClass.TreeNode;

/**
 * 450. 删除二叉搜索树中的节点
 *
 *
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 *
 * 一般来说，删除节点可分为两个步骤：
 *
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 *
 *
 * 示例 1:
 *
 *
 *
 * 输入：root = [5,3,6,2,4,null,7], key = 3
 * 输出：[5,4,6,2,null,null,7]
 * 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
 * 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
 * 另一个正确答案是 [5,2,6,null,4,null,7]。
 *
 *
 * 示例 2:
 *
 * 输入: root = [5,3,6,2,4,null,7], key = 0
 * 输出: [5,3,6,2,4,null,7]
 * 解释: 二叉树不包含值为 0 的节点
 * 示例 3:
 *
 * 输入: root = [], key = 0
 * 输出: []
 *
 *
 * 提示:
 *
 * 节点数的范围 [0, 104].
 * -105 <= Node.val <= 105
 * 节点值唯一
 * root 是合法的二叉搜索树
 * -105 <= key <= 105
 *
 *
 * 进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
 *https://leetcode.cn/problems/delete-node-in-a-bst/?envType=study-plan-v2&envId=leetcode-75
 */
public class T450_删除二叉搜索树的节点 {

    // 二插搜索树 是平衡树 ，
    //一共三种情况 1.左子叶为空 右子叶补上，2.右子叶为空 左子叶补上 3.左右子叶都不为空 让右子树最左节点补上
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        //相等则找到删除节点
        if (root.val == key) {
            //分三种情况：
            //第一种是待删除节点的左右子节点都为null
            //第二种是待删除的节点的左节点为null或右节点为null
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            //第三种左右子节点都不为null
            //使用循环 找到最小的节点 有左节点 向左寻找 没有左节点该节点就是最小节点
            TreeNode temp = root.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            //删除右子树的最小节点
            root.right = deleteNode(root.right,temp.val);
            temp.left = root.left;
            temp.right = root.right;
            root = temp;

        }
        else if (root.val > key) {
            root.left = deleteNode(root.left,key);
        }
        else if (root.val < key) {
            root.right = deleteNode(root.right,key);
        }
        return root;
    }
}
